#include <bits/stdc++.h>
#include "BalanceTree.h"
using namespace std;

template <class T>
void AVL_sort(vector <T> & v){
	AvlTree <T> t;
	for(int i = 0; i < v.size(); i++) t.insert(v[i]);
	v.clear();
	while(!t.isEmpty()){
        T x=t.findMin();
        t.remove(x);
        v.push_back(x);
    }
}

template <class T>
void Splay_sort(vector <T> & v){
	SplayTree <T> t;
	for(int i = 0; i < v.size(); ++i) t.insert(v[i]);
	v.clear();
	while(!t.isEmpty()){
        T x=t.findMin();
        t.remove(x);
        v.push_back(x);
    }
}

int n;
vector <int> v1, v2;
int main() {
	cin >> n;
	v1.resize(n);
	for(int i = 0; i < n; ++i) cin >> v1[i];
	
	double begin, end;
	
	v2=v1;
	begin = clock();
	AVL_sort(v2);
	end = clock();
	for(int i = 0; i < n; ++i) cout << v2[i] << ' ';
	cout << endl;
	cout << "AVL_sort_time = " << end - begin << endl;
	
	v2=v1;
	begin = clock();
	Splay_sort(v2);
	end = clock();
	for(int i = 0; i < n; ++i) cout << v2[i] << ' ';
	cout << endl;
	cout << "Splay_sort_time = " << end - begin << endl;
}